package other;

import common.Util;
import common.ListNode;

public class Link {

    /**
     * 反转链表
     * 
     * @param head
     * @return
     */
    public static ListNode reverseListNode(final ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            final ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    public static ListNode reverseListNode2(ListNode listNode) {
        return recursive(null, listNode);
    }

    /**
     * 递归反转链表
     * 
     * @param head
     * @param listNode
     * @return
     */
    public static ListNode recursive(final ListNode head, ListNode listNode) {
        if (listNode == null)
            return head;
        ListNode next = listNode.next;
        listNode.next = head;
        return recursive(listNode, next);
    }

    public static void main(final String[] args) {
        ListNode listNode = reverseListNode2(Util.createListNode());
        StringBuilder result = new StringBuilder();
        while (listNode != null) {
            result.append(listNode.val + " -> ");
            listNode = listNode.next;
        }
        result.append("null");
        System.out.println(result.toString());
    }
}